package sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class MergeSort {

    public static void mergeSort(int[] arr){
        if(arr == null || arr.length <= 1){
            return;
        }
        int n = arr.length;
        mergeSort(arr, 0, n-1);
    }

    private static void mergeSort(int[] arr, int left, int right){
        if(left == right){
            return;
        }
        int mid = (left + right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right-left+1];
        int i = 0;          //临时数组指针
        int p1 = left;      //左序列指针
        int p2 = mid + 1;   //右序列指针
        while(p1 <= mid && p2 <= right){
            if(arr[p1] < arr[p2]){
                temp[i++] = arr[p1++];
            } else {
                temp[i++] = arr[p2++];
            }
        }
        while (p1 <= mid){          //将左边剩余元素填充进temp中
            temp[i++] = arr[p1++];
        }
        while (p2 <= right){        //将右序列剩余元素填充进temp中
            temp[i++] = arr[p2++];
        }

        //将temp中的元素全部拷贝到原数组中
        for(i = 0; i<temp.length; i++){
            arr[left + i] = temp[i];
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
//        selectionSort(arr);
        mergeSort(arr);
        System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    }
}
